package leetcode101_xqzhao

// 从前序与中序遍历序列构造二叉树 【-】 递归[经典]

func buildTree(preorder []int, inorder []int) *TreeNode {
	var res *TreeNode

	var dfs105 func(pre []int, mid []int) *TreeNode
	dfs105 = func(pre []int, mid []int) *TreeNode {
		// 递归终止条件
		n := len(pre)
		if n == 0 {
			return nil
		}
		// 继续递归 + 保存结果
		var tmpNode = &TreeNode{Val: pre[0]}
		i := 0
		for ; i < len(mid); i++ {
			if mid[i] == pre[0] {
				break
			}
		}
		tmpNode.Left = dfs105(pre[1:1+i], mid[:i])
		tmpNode.Right = dfs105(pre[1+i:], mid[i+1:])
		return tmpNode
	}

	res = dfs105(preorder, inorder)

	return res
}
